package Interview;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Scanner;

/**
 * Created by Administrator on 2017/4/1.
 *
 *
 *有一个单词列表，一个初始单词和一个最终单词，初始单词需要通过单词列表逐步变换到最终单词，求变换所需的最短变换路径长度。
 变换规则：每次只能变动1个字母（不可交换位置，如：从abc变成cba属于变动了2个字母），每次变换只能从单词列表中选取。
 例如：初始单词hot，最终单词dog，单词列表[got, dot, god, dog, lot, log]，最短变换路径为[hot,dot,dog]，最短变换路径长度为3。
 注：单词列表中包含最终单词，不包含初始单词；列表中每一项单词长度与初始单词、最终单词相同；列表中单词不重复；所有字母均为小写。
 *
 * 输入
 输入数据有三行，第一行为初始单词；第二行为最终单词；第三行为单词列表，单词和单词之间以空格分割。

 输出
 最短变换路径长度。


 样例输入
 hot
 dog
 got dot god dog lot log

 样例输出
 3

 Hint
 寻找最短路径相关算法。
 *
 *
hot
dog
got dot god dog lot log
 */

class mytu{
    String name;
    LinkedList<mytu> adj;
    int path;

    public mytu(String nm){
        name=nm;
        path = Integer.MAX_VALUE;
        adj =new LinkedList<mytu>();
    }
}

public class _qunawang_20170401Test2 {

    public static boolean compare(String a,String b){
        int count = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)){
                count++;
                if (count>1)
                    return false;
            }
        }
        return count != 0;


    }

    public static void find(mytu Tu, String target){
        if (Tu.name.equals(target)){
            return;
        }
        for (mytu next:
                Tu.adj) {
            if (next.path>Tu.path + 1){
                next.path  = Tu.path + 1;
                find(next,target);
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String first = in.nextLine().trim();
            String end = in.nextLine().trim();
            String[] words = in.nextLine().trim().split(" ");

            Map<String,mytu> map = new HashMap<>();
            for (String s:
                 words) {
                map.put(s,new mytu(s));
            }
            //构建无权无向图
            for (String s:
                    words) {
                for (String t:
                        words){
                    if (compare(s,t))
                    map.get(s).adj.add(map.get(t));
                }
            }

            mytu startTu = new mytu(first);
            for (String t:
                    words){
                if (compare(first,t))
                    startTu.adj.add(map.get(t));
            }
            startTu.path = 1;
            find(startTu,end);

            System.out.println(map.get(end).path);
        }

    }

}
